package likou.offer;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Info:
 * @Author: 唐小尊
 * @Date: 2020/8/21  20:21
 */
public class _38_niubi {
    public static void main(String[] args) {
        for (String str : permutation("abcc")){
            System.out.println(str);
        }
    }

    static List<String> list = new ArrayList<>();

    public static String[] permutation(String s) {
        char[] ori = s.toCharArray();

        helper(ori, 0);
        return list.toArray(new String[0]);
    }

    private static void helper(char[] all, int index) {
        if (index == all.length) {
            String s = new String(all);
            list.add(s);
        }

        for (int i = index; i < all.length; i++) {
            if (i == index) {   // 同一个下标，无需交换
                helper(all, index+1);
                continue;
            }

            int k;
            for (k = i-1; k >= index; k--) {    // 剔除重复
                if (all[k] == all[i]) {
                    break;
                }
            }

            if (k != index-1) {
                continue;
            }

            swap(all, i, index);
            helper(all, index+1);
            swap(all, i, index);
        }
    }

    private static void swap(char[] all, int i, int j) {
        char tmp = all[i];
        all[i] = all[j];
        all[j] = tmp;
    }
}
